|
In additive number theory and combinatorics, a restricted sumset has the form : where are finite nonempty subsets of a field ''F'' and is a polynomial over ''F''. When , ''S'' is the usual sumset which is denoted by ''nA'' if ; when : ''S'' is written as which is denoted by if . Note that |''S''| > 0 if and only if there exist with . == Cauchy-Davenport theorem == The Cauchy–Davenport theorem named after Augustin Louis Cauchy and Harold Davenport asserts that for any prime ''p'' and nonempty subsets ''A'' and ''B'' of the prime order cyclic group Z/''p''Z we have the inequality〔Nathanson (1996) p.44〕〔Geroldinger & Ruzsa (2009) pp.141–142〕 : We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2''n''−1 elements in Z/''n'', there are ''n'' elements that sums to zero modulo ''n''. (Here ''n'' does not need to be prime.)〔Nathanson (1996) p.48〕〔Geroldinger & Ruzsa (2009) p.53〕 A direct consequence of the Cauchy-Davenport theorem is: Given any set ''S'' of ''p''−1 or more elements, not necessarily distinct, of Z/''p''Z, every element of Z/''p''Z can be written as the sum of the elements of some subset (possibly empty) of ''S''.〔Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.〕 Kneser's theorem generalises this to finite abelian groups.〔Geroldinger & Ruzsa (2009) p.143〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Restricted sumset」の詳細全文を読む スポンサード リンク
|